1. Field of the Invention
This invention relates to binary multibit multipliers and more particularly to such multipliers which use recoding.
The invention finds particular utility in signal processors and other computer systems and is particularly adapted to be integrated into the device producing the signals to be processed such as I/0 controllers and microprocessors as well as in large computer systems.
2. Description of the Prior Art
Digital multipliers for multiplication of signed binary numbers are generally slow and require large amounts of circuitry as the size, i.e. the number of inputs, increases. This is because as the size increases the number of adders required or the complexity thereof for implementation of the multiplier increases. Therefore it is desirable to devise some way to reduce the number of additions required to complete the multiplication and to do so in a simple manner to keep multiplication time and circuitry to a minimum. Recoding of the binary inputs can reduce the number of additions required to complete the multiplication because two or more bits of the multiplier can be recoded so as to require only one addition for the recoded bits rather than an addition for each bit of the multiplier. Also, recoding allows positive and negative multipliers to be treated in the same manner. Bit pair recoding has been used in the past and it only requires simple shifts and/or complements of the multiplicand. Recoding schemes larger than bit pair recoding become more complex and require more forms of the multiplicand to be available to the rows of adders. The present invention uses four bit recoding and generates all multiples of the multiplicand in a manner to minimize circuit area and to provide a speed advantage. This is accomplished by generating all multiples of the multiplicand in a unique manner whereby simple adders, i.e. adders capable of forming the sum of two binary numbers rather than adders which can add three binary numbers at the same time, are used.